package com.suanfa.island;

/**
 * 省份个数，[i][j]代表 i市连接j市 j市连接m市 直接+间接相连看做一个省
 */
public class ProvinceCount {
    public static void main(String[] args) {
        int[][] arr= {{1,0,0,1},{0,1,1,0},{0,1,1,1},{1,0,1,1}};
        int[][] arr1= {{1,1,0},{1,1,0},{0,0,1}};
        System.out.println(getProvince(arr1));
    }

    public static int getProvince(int[][] arr){
        int count = 0;
        for(int i=0; i< arr.length; i++){
            for(int j = 0; j<arr[0].length; j++){
                if(arr[i][j] == 1){
                    dfs(arr, j);
                    count++;
                }
            }
        }
        return count;
    }

    static void dfs(int[][] arr, int r){
        for(int i=0; i< arr[0].length; i++){
            if(arr[r][i] == 1){
                arr[r][i]=2;
                dfs(arr, i);
            }
        }

    }
}
